import java.util.Arrays;
import java.util.Comparator;

public class Solution {
    public static void main(String[] args) {
        Solution test = new Solution();
        int[][] p = new int[][]{{1,2}, {2,3}, {3,4}};
        System.out.println(test.findLongestChain(p));
    }

    public int findLongestChain(int[][] p) {
        /**
         * 状态表示：
         *      dp[i]表示以i下标元素为结尾的所有数对链，最长数对链的长度
         * 状态表示：
         *      向前遍历，遇见第一个，赋值后返回
         *      if(p[i][0] > p[j][1]) {
         *          dp[i] = dp[j] + 1;
         *      }
         * 初始化：
         *      由题，单个数对也可视为数对链，长度为1，故将dp表全部初始化为1
         *      并且为了减少遍历，因此将数对按照第一个元素的大小进行排序
         * 填表顺序：
         *      从左往右
         * 返回值：
         *      返回dp表中最大值
         *      */
        // 1 预处理
        int n = p.length;
        // 将数组按照第一列的元素大小进行排序
        Arrays.sort(p, Comparator.comparingInt(a -> a[0]));
        // 2 创建dp表
        int[] dp = new int[n];
        // 3 初始化
        Arrays.fill(dp, 1 );
        // 4 填表
        int maxLength = 1;
        for(int i = 1; i < n; i ++) {
            for(int j = i-1; j >= 0; j--) {
                if(p[i][0] > p[j][1]) {
                    dp[i] = dp[j] + 1;
                    if(dp[i] > maxLength) maxLength = dp[i];
                    break;
                }
            }
        }
        // 5 返回值
        return maxLength;
    }
}
